#include <cstdlib>
#include <iostream>
#include <string>
#define YELLOW "\033[33m" /* Yellow */
#define WHITE "\033[37m"  /* White */
#define RESET "\033[0m"
using namespace std;

#ifdef LINUX
#define CLEARFUN system("clear")
#else
#define CLEARFUN system("cls")
#endif

const int N = 225;   // 棋盘总的格子数
const int M = 15;    // 棋盘每行的格子数
const int ALPHA = 1; // 攻击性因数，越高代表进攻欲望越强
const int POSITIVE_INFINITY = 0x3f3f3f3f;
const int NEGATIVE_INFINITY = -POSITIVE_INFINITY;
const char MACHINECHESS = '&'; // 机器的棋子
const char HUMANCHESS = '+';   // 人类棋子

// 方向数组，分别代表水平，纵向，主对角线，副对角线
const int DIRECTION[4][4] = {
    {0, -1, 0, 1}, {-1, 0, 1, 0}, {-1, -1, 1, 1}, {-1, 1, 1, -1}};

// 地形数组，我们认为，越靠近中心的点对于下棋越有优势
const int PosValue[M][M] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                            {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0},
                            {0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0},
                            {0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0},
                            {0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 0},
                            {0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0},
                            {0, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 0},
                            {0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, 0},
                            {0, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 0},
                            {0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0},
                            {0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 0},
                            {0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0},
                            {0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0},
                            {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0},
                            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

pair<int, int> valarry[4000]; // 记录每种情况下棋盘的价值，当作栈处理
int top = 0;                  // 栈顶
int history[200]; // 记录下棋的每一步，用于恢复旧状态

int LEVEL = 4; //
int Edge[10] = {NEGATIVE_INFINITY, POSITIVE_INFINITY, NEGATIVE_INFINITY,
                POSITIVE_INFINITY, NEGATIVE_INFINITY, POSITIVE_INFINITY,
                NEGATIVE_INFINITY, POSITIVE_INFINITY, NEGATIVE_INFINITY};

char chess_board_init[N]; // 棋盘

// 结构体没有任何用处，暂时 22/11/29 22:26:06
struct state_chess {
    // 使用 100 个 char 类型储存棋盘每个位置的状态
    // . 空位置
    // & 敌方棋子
    // + 我方棋子
    char pos[N];
    int value;
};

pair<int, int> value_chess(char *arr); // 对当前棋盘做价值评估

bool alpha_beta_reduce(int step, int value);

int cal_pos_val(int x, int y, char *arr); // 对于给定的一个位置 (x,y)
                                          // 和一个给定的棋盘，arr
                                          // 计算这个位置上的棋子的价值
// 这里的评估标准就是认为
// 每个位置四个方向，连续的相同的棋子
// 具有价值
string buildStr(int x, int y, char *arr,
                int dir); // 根据之前的方向数组
                          // 在给定的位置 (x,y)
                          // 和给定的棋盘 arr
                          // 构造水平，纵向，主对角线
                          // 副对角线，四个方向的连续字符串

pair<int, int> max_value(pair<int, int> *value, int start,
                         int end); // 取所有子节点价值最大的
pair<int, int> min_value(pair<int, int> *value, int start,
                         int end); // 取所有子节点价值最小的

bool isValid(int x, int y); // 判断下是否出界

int counter(int x, int y, int xDir, int yDir, char *chessBoard);

bool isGameOver(int x, int y, char *arr); // 判断游戏是否结束，产生胜利者

void printchess(char *arr, int x, int y); // 打印当前棋盘状态

pair<int, int> expand_chess(char *arr, int step) {
    // 最大最小搜索
    // arr 是棋盘
    // step 是预测到第几步
    step++;
    pair<int, int> result; // 返回的是一个 pair
                           // 前一个 int 代表，下一个某一个棋子后棋盘的价值
                           // 后一个 int 代表，棋子下到那个位置

    if (step > LEVEL) {
        return value_chess(arr); // 最多预测 4 步就返回
    }

    char chess =
        (step % 2) ? HUMANCHESS : MACHINECHESS; // step 为奇数，轮到我方下棋
                                                // step 为偶数，轮到敌方下棋
                                                // 注意玩的时候，人类代表敌方

    int start = top; // 栈顶，后面会清空栈，所以先保留
                     // FOR DEBUG
    if (top >= 3900) {
        cout << "\nError! top more than 3900\n";
    }
    // END DEBUG
    for (int i = 0; i < N; i++) {
        if (arr[i] == 0) {
            arr[i] = chess; // 下棋
            valarry[top] = expand_chess(arr, step);
            valarry[top].second = i; // 下棋到第 i 个位置 i = x * M + y
            top++;                   // 栈中数据增加一个
            arr[i] = 0;              // 恢复棋盘

            if (alpha_beta_reduce(step, valarry[top].first)) {
                break; // 后续节点已经不需要扩展
            }
        }
    }

    result = (step % 2) ? max_value(valarry, start, top)
                        : min_value(valarry, start, top);

    // 奇数取最大，一个与节点
    // 偶数取最小，一个或节点
    top = start;    // 栈清空
    if (step % 2) { // 我方下棋 敌方选择最小的值
        Edge[step] = (Edge[step] < result.first) ? Edge[step] : result.first;
    } else { // 敌方下棋 我方选择最大的值
        Edge[step] = (Edge[step] > result.first) ? Edge[step] : result.first;
    }
    return result;
}

int main(int argc, char *argv[]) {
	if (argc == 2){
		LEVEL = atoi(argv[1]);
		if (LEVEL > 10 || LEVEL < 0){
			LEVEL = 4;
		}
	}
    pair<int, int> decision; // 决策
    int x; // 人类玩家输入的下棋位置，第 x 行，第 y 列，均从 0 开始数
    char y; // y 是字母 a b c ...
    //===============================================================================
    CLEARFUN;
    cout << "Welcome to gomoku! The Level is " << LEVEL << ".\n"
         << "& stand for enemy，+ stand for you.\nInput format: digital "
            "letter.\n"
         << "For example: 1a, 11b" << endl;
    //===============================================================================
    chess_board_init[7 * M + 7] = MACHINECHESS;
    printchess(chess_board_init, 7, 7);
    //===============================================================================
    while (true) {

        // 边界初始化
        for (int i = 0; i < 10; i++) {
            if (i % 2) {
                Edge[i] = POSITIVE_INFINITY;
            } else {
                Edge[i] = NEGATIVE_INFINITY;
            }
        }
        //===============================================================================
        while (true) {
            cout << "\nHuman Decision: ";
            cin >> x >> y;
            x = x % M;
            y = y - 'a';
            y = y % M;

            if (isValid(x, y) && chess_board_init[x * M + y] == 0) {
                chess_board_init[x * M + y] = HUMANCHESS; // 人类后手下棋

                CLEARFUN;
                cout << "& stand for enemy，+ stand for you.\nInput format: "
                        "digital letter.\n"
                     << "For example: 1a, 11b" << endl;

                printchess(chess_board_init, x, y);
                break;
            } else {
                cout << "Input error, do it again." << endl;
            }
        }
        if (isGameOver(x, y, chess_board_init)) {
            cout << "The game is over. Human win." << endl;
            break;
        }
        //==============================================================================
        decision = expand_chess(chess_board_init, 0);
        int posAIx = decision.second / M;
        char posAIy = decision.second % M + 'a';
        chess_board_init[decision.second] = MACHINECHESS; // 程序先手下棋
        cout << "\nMachine Decision: " << decision.first << " (" << posAIx
             << ", " << posAIy << ")" << endl;

        CLEARFUN;
        cout << "& stand for enemy，+ stand for you.\nInput format: digital "
                "letter.\n"
             << "For example: 1a, 11b" << endl;
        printchess(chess_board_init, posAIx, posAIy - 'a');

        if (isGameOver(posAIx, posAIy - 'a', chess_board_init)) {
            cout << "The game is over. Machine win." << endl;
            break;
        }
        //==============================================================================
    }
    return 0;
}

bool alpha_beta_reduce(int step, int value) {
    if (step % 2 == 1) { // 我方下棋
        if (value > Edge[step]) {
            return true; // 当前值大于旧下界，说明上层或节点将不会选择这个合子节点
                         // 因为当前是合子节点，最终选择一个最大值返回给上层
        } else {
            return false; // 当前值小于旧下界，旧下界可能需要更新
        }
    } else { // 敌方下棋
        if (value < Edge[step]) {
            return true; // 当前值小于旧上界，说明上层与节点不会选择这个或子节点
                         // 因为当前是或子节点，最终选择一个最小值返回给上层
        } else {
            return false; // 当前值大于旧上界，旧上界可能需要更新
        }
    }
    return false; // 默认 false ，保证尽可能遍历所有点
}

pair<int, int> value_chess(char *arr) {
    int ally = 0;  // 我方得分
    int enemy = 0; // 敌方得分
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            char c = arr[i * M + j];
            if (c == HUMANCHESS) {
                ally += cal_pos_val(i, j, arr);
            } else if (c == MACHINECHESS) {
                enemy += cal_pos_val(i, j, arr);
            }
        }
    }
    pair<int, int> res;
    res.first = ALPHA * ally - enemy;
    return res;
}

int cal_pos_val(int x, int y, char *arr) {
    // 这部分很长，是抄的，根据不同的形状给不同的分数
    const int CHENG_5_SCORE = 5000000;
    const int HUO_4_SCORE = 100000;
    const int CHONG_4_SCORE = 10000;
    const int DAN_HUO_3_SCORE = 8000;
    const int TIAO_HUO_3_SCORE = 7000;
    const int MIAN_3_SCORE = 500;
    const int HUO_2_SCORE = 50;
    const int MIAN_2_SCORE = 10;
    string CHENG_5_STRING = "11111";
    string HUO_4_STRING = "011110";
    string CHONG_4_STRING_1_1 = "01111-";
    string CHONG_4_STRING_1_2 = "-11110";
    string CHONG_4_STRING_2_1 = "10111";
    string CHONG_4_STRING_2_2 = "11101";
    string CHONG_4_STRING_3 = "11011";
    string DAN_HUO_3_STRING = "01110";
    string TIAO_HUO_3_STRING_1_1 = "1011";
    string TIAO_HUO_3_STRING_1_2 = "1101";
    string MIAN_3_1_1 = "00111-";
    string MIAN_3_1_2 = "-11100";
    string MIAN_3_2_1 = "01011-";
    string MIAN_3_2_2 = "-11010";
    string MIAN_3_3_1 = "01101-";
    string MIAN_3_3_2 = "-10110";
    string MIAN_3_4_1 = "10011";
    string MIAN_3_4_2 = "11001";
    string MIAN_3_5 = "10101";
    string MIAN_3_6 = "-01110-";
    string HUO_2_STRING_1 = "001100";
    string HUO_2_STRING_2 = "01010";
    string HUO_2_STRING_3 = "1001";
    string MIAN_2_1_1 = "00011-";
    string MIAN_2_1_2 = "-11000";
    string MIAN_2_2_1 = "00101-";
    string MIAN_2_2_2 = "-10100";
    string MIAN_2_3_1 = "01001-";
    string MIAN_2_3_2 = "-10010";
    string MIAN_2_4 = "10001";

    int score = 0;
    int weight = PosValue[x][y];
    for (int dir = 0; dir < 4; dir++) {
        string s = buildStr(x, y, arr, dir); // 先沿着给定方向构造字符串

        // 如果构建出来的字符串中包含“成五”的子串，加上其分数
        if (s.find(CHENG_5_STRING) != string::npos) {
            score += CHENG_5_SCORE;
#ifdef DEBUG_USE_ONLY
            printf("Found: %s : %d \n", "CHENG_5", score);
#endif
        }

        // 如果包含“活四”的子串，加上其分数
        if (s.find(HUO_4_STRING) != string::npos) {
            score += HUO_4_SCORE;
#ifdef DEBUG_USE_ONLY
            printf("Found: %s : %d \n", "HUO_4", score);
#endif
        }

        // “冲四”不止一种情况，如果包含任意一个子串，加上其分数，下面的情况同理
        if (s.find(CHONG_4_STRING_1_1) != string::npos ||
            s.find(CHONG_4_STRING_1_2) != string::npos ||
            s.find(CHONG_4_STRING_2_1) != string::npos ||
            s.find(CHONG_4_STRING_2_2) != string::npos ||
            s.find(CHONG_4_STRING_3) != string::npos) {
            score += CHONG_4_SCORE;
#ifdef DEBUG_USE_ONLY
            printf("Found: %s : %d \n", "CHONG_4", score);
#endif
        }

        if (s.find(DAN_HUO_3_STRING) != string::npos) {
            score += DAN_HUO_3_SCORE;
#ifdef DEBUG_USE_ONLY
            printf("Found: %s : %d \n", "DAN_HUO_3", score);
#endif
        }

        if (s.find(TIAO_HUO_3_STRING_1_1) != string::npos ||
            s.find(TIAO_HUO_3_STRING_1_2) != string::npos) {
            score += TIAO_HUO_3_SCORE;
#ifdef DEBUG_USE_ONLY
            printf("Found: %s : %d \n", "TIAO_HUO_3", score);
#endif
        }

        if (s.find(MIAN_3_1_1) != string::npos ||
            s.find(MIAN_3_1_2) != string::npos ||
            s.find(MIAN_3_2_1) != string::npos ||
            s.find(MIAN_3_2_2) != string::npos ||
            s.find(MIAN_3_3_1) != string::npos ||
            s.find(MIAN_3_3_2) != string::npos ||
            s.find(MIAN_3_4_1) != string::npos ||
            s.find(MIAN_3_4_2) != string::npos ||
            s.find(MIAN_3_5) != string::npos ||
            s.find(MIAN_3_6) != string::npos) {
            score += MIAN_3_SCORE;
#ifdef DEBUG_USE_ONLY
            printf("Found: %s : %d \n", "MIAN_3", score);
#endif
        }
        if (s.find(HUO_2_STRING_1) != string::npos ||
            s.find(HUO_2_STRING_2) != string::npos ||
            s.find(HUO_2_STRING_3) != string::npos) {
            score += HUO_2_SCORE;
#ifdef DEBUG_USE_ONLY
            printf("Found: %s : %d \n", "HUO_2", score);
#endif
        }

        if (s.find(MIAN_2_1_1) != string::npos ||
            s.find(MIAN_2_1_2) != string::npos ||
            s.find(MIAN_2_2_1) != string::npos ||
            s.find(MIAN_2_2_2) != string::npos ||
            s.find(MIAN_2_3_1) != string::npos ||
            s.find(MIAN_2_3_2) != string::npos ||
            s.find(MIAN_2_4) != string::npos) {
            score += MIAN_2_SCORE;
#ifdef DEBUG_USE_ONLY
            printf("Found: %s : %d \n", "MIAN_2", score);
#endif
        }
    }
    return score * weight + weight;
}

string buildStr(int x, int y, char *chessBoard, int dir) {
    string s = "";
    // 计算该方向上的起始点坐标
    int rBegin = x + DIRECTION[dir][0] * 4;
    int cBegin = y + DIRECTION[dir][1] * 4;
    // 坐标递增的方向
    int rDir = DIRECTION[dir][2];
    int cDir = DIRECTION[dir][3];
    // 计算该方向上的终止点坐标
    int rEnd = x + rDir * 4;
    int cEnd = y + cDir * 4;
    // 当行列没到终点的时候（表示没有收集齐9个点），循环
    int r = rBegin;
    int c = cBegin;
    char pattern = chessBoard[x * M + y];
    while (r != rEnd || c != cEnd) {
        // 如果这个点没有超过棋盘范围，是自己就记为1，是空记为0，是对手记为-，超过棋盘的点记为#
        if (isValid(r, c))
            if (chessBoard[r * M + c] == pattern)
                s += "1";
            else if (chessBoard[r * M + c] == 0)
                s += "0";
            else
                s += "-";
        else
            s += "#";
        r += rDir;
        c += cDir;
    }
    return s;
}

pair<int, int> max_value(pair<int, int> *value, int start, int end) {
    pair<int, int> res = value[start];
    for (int i = start + 1; i < end; i++) {
        if (res.first < value[i].first) {
            res = value[i];
        }
    }
    return res;
}

pair<int, int> min_value(pair<int, int> *value, int start, int end) {
    pair<int, int> res = value[start];
    for (int i = start + 1; i < end; i++) {
        if (res.first > value[i].first) {
            res = value[i];
        }
    }
    return res;
}

bool isValid(int x, int y) { return (x >= 0 && x < M && y >= 0 && y < M); }

int counter(int x, int y, int xDir, int yDir, char *chessBoard) {
    // 计算每个方向上的连续的棋子个数
    int cnt = 0;
    int chess = chessBoard[x * M + y];
    int r = x + xDir;
    int c = y + yDir;
    while (isValid(r, c) && chessBoard[r * M + c] == chess) {
        r += xDir;
        c += yDir;
        cnt++;
    }
    return cnt;
}

bool isGameOver(int x, int y, char *arr) {
    for (int dir = 0; dir < 4; dir++) {
        int cnt = 1;
        cnt += counter(x, y, DIRECTION[dir][0], DIRECTION[dir][1], arr);
        cnt += counter(x, y, DIRECTION[dir][2], DIRECTION[dir][3], arr);
        if (cnt >= 5) {
            return true;
        }
    }
    return false;
}
void printchess(char *arr, int x, int y) {
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i * M + j] == 0) {
                cout << '.';
            } else {
                if (i == x && j == y && arr[i * M + j] == MACHINECHESS) {
                    cout << YELLOW << MACHINECHESS << RESET;
                } else {
                    cout << arr[i * M + j];
                }
            }
            cout << ' ';
        }
        cout << i << '\n';
    }

    char temp = 'a';
    for (int i = 0; i < M; i++) {
        cout << temp++ << ' ';
    }
    cout << "\n================================\n";
}
